Learning Petit Lesson 4b: Advanced array topics
This is an advanced tutorial. New programmers might want to skip this and come back to it later This lesson covers some of the more powerful things you can do with arrays. If you need to add to or remove from your array, or track a limited number of objects that can change over time (such as enemies on the screen), this is where you want to start. Some ideas To make the next few topics easier to understand let's come up with some new terms related to arrays: I will say an array has static content if it starts out filled and few or no changes are made to the content. I will say an array has dynamic content if we will be "adding to" or "removing from" the array. These are my own terms for ease of clarity in this article (see notes for more info). Now keep in mind that we can't actually change the size of an array in Petit (see notes again), but in some cases we don't use the whole thing at once. Let me give some examples to make these terms more clear: With a 1D array, static content might be array that holds 5 names that never change. Dynamic content might be an empty list of friends and every time the user adds a friend, you put it in the next available index. Now for 2D arrays. Say you had a game with 5 types of enemies, 10 rooms and exactly 3 enemies in each room. With static content you might have an array with 30 rows, one for each enemy in the game. As you can see, this is wasteful, and doesn't work well if your game has 500 enemies. With dynamic contents, you could just use one array with 3 rows that store the enemies in the current room; when the player changes rooms, you just replace the enemies in the array! With this approach, you would probably use templates, covered below. "Growing" and "shrinking" arrays Using the list of friends example yet again, let's think more about the implementation. You start out with an array that has enough space for a decent number of friends, but no friends in it at the start. We want to be able to add friends to the end of the list, so we need to track how many friends are currently in the list. :MAXFRIENDS = 32 :DIM FRIENDS$(MAXFRIENDS) :NUMFRIENDS = 0 Since arrays in Petit are 0-indexed, NUMFRIENDS also tells us the index where we would add the next friend! :@ADDFRIEND :IF (NUMFRIENDS MAXFRIENDS) THEN PRINT "ERROR: Array is full!" : END :FRIENDS$(NUMFRIENDS) = NEWFRIEND$ :NUMFRIENDS = NUMFRIENDS + 1 :RETURN To print out the list, we only print the elements in "valid" indexes :@PRINTFRIENDS :FOR X = 0 TO NUMFRIENDS - 1 :PRINT FRIENDS$(X) :NEXT :RETURN If we want to "delete" the last friend in the list, we just do NUMFRIENDS = NUMFRIENDS - 1. Although the name that was in that index is still in the array, it won't be used. The next time @ADDFRIEND is called, the new name will replace the one in that index. Simple! 'Deleting an arbitrary index in a 1D array' What if the user wants to delete the 3rd friend in a list of five friends? Here are two different ways to do this: Shifting: With shifting, we move each element after the deleted element over to fill the space. :@DELETEFRIEND :IF (INDEX >= NUMFRIENDS) THEN PRINT "ERROR: Invalid index" : RETURN :NUMFRIENDS = NUMFRIENDS - 1 :'if index was the last element, we're already done :IF (INDEX NUMFRIENDS) THEN RETURN :FOR X = INDEX TO NUMFRIENDS - 1 :FRIEND$(X) = FRIEND$(X + 1) :NEXT :NUMFRIENDS = NUMFRIENDS - 1 :RETURN This approach keeps our array nice and tidy but it might be slow if you have to shift a large number of elements. Invalidation: With invalidation, each element in an array might be 'valid' or 'invalid' and to 'delete' an element we just make it invalid. This requires a fairly different approach, as well as a way to mark elements as invalid. For an array of names, you could treat an empty string "" as invalid: :@DELETEFRIEND :FRIENDS$(INDEX) = "" :RETURN As you can see, deletion via invalidating is extremely easy, but our former approach to adding and printing wouldn't work! We have to change those: :@ADDFRIEND :FOR X = 0 TO MAXFRIENDS - 1 :IF (NAMES$(X) "") THEN NAMES$(X) = NEWFRIEND$ : RETURN :NEXT :PRINT "ERROR: Array is full!" : END : :@PRINTFRIENDS :FOR X = 0 TO MAXFRIENDS - 1 :IF (FRIENDS$(X) != "") PRINT FRIENDS$(X) :NEXT :RETURN With this approach, any index in the array might contain a valid or invalid element, so we check whether each element is valid when looping through the array. If we're adding a new element, we can stick it in the first 'open' (invalid) index and return. Invalidation makes a performance tradeoff - we do much less work when deleting something from the array, but we do more work when adding to or printing the array. This implementation of invalidation requires there to be some type of invalid value. With strings, that's often an empty string. In an array of numbers, invalidation can be trickier. If only positive values are allowed, any negative value (typically -1) can be used to mark an index as invalid. Sometimes no value will work as "invalid", if that's the case, we can use a parallel array (see previous lesson) to track which elements are valid. Whether to use shifting or invalidation depends partly on what you're doing and partly on preference. If you are working with small arrays the performance difference probably doesn't matter. In general, shifting is better if you'll be looping through the whole array frequently, while invalidation is better if you'll usually be referring to individual elements. :Tip: You don't have to use a variable to track the number of elements in the array when using invalidation, but it's a good idea since it makes it easier to check whether the array is full. In the @ADDFRIEND subroutine, we could skip the for loop entirely if we already knew the array was full. Invalidation with 2D arrays Using a 2D array with the invalidation principle is a great approach if you'll have a limited number of some type of object in use at once and want to conserve memory. Say you have a game where there might be anywhere between 0 and 5 enemies onscreen at once; a new enemy will appear every few seconds if there is space available. :HP = 0 : DMG = 1 : SPD = 2 'index names :MAXENEMIES = 5 :DIM ENEMIES(MAXENEMIES, 3) :... :@ADDENEMY :FOR X = 0 to MAXENEMIES - 1 :IF (ENEMIES(X, HP) < 1) GOSUB @INSERTENEMY : RETURN :NEXT :RETURN 'no room for new enemy : :@INSERTENEMY :ENEMIES(X, HP) = HEALTH :ENEMIES(X, DMG) = DAMAGE :ENEMIES(X, SPD) = SPEED :RETURN Here we use a nifty trick - we use the enemy's health to see if it's invalid. If it has less than 1 health, it's dead, and we can put a new enemy there. When we do this, we obviously have to have the health, damage, and speed of the new enemy ready to insert into the array. We can set up these values using templates: 'Templates' Say we have an array of 5 active enemies, and several different types of enemies that might go into that array. Two approaches are template subroutines and template arrays: Template subroutine: :@ADDSOLDIER :HEALTH = 5 :DAMAGE = 1 :SPEED = 1 :GOSUB @ADDENEMY :RETURN Template array: :SOLDIER = 0 :TANK = 1 :NUMENEMYVALS = 3 :DIM ETEMPLATE(2, NUMENEMYVALS) :GOSUB @FILLTEMPLATE :... :IF (TIMETOADDSOLDIER) THEN ETYPE=SOLDIER : GOSUB @ADDENEMY :IF (TIMETOADDTANK) THEN ETYPE=TANK : GOSUB @ADDENEMY :... :' Same @ADDENEMY as above : :@INSERTENEMY :FOR Y = 0 TO NUMENEMYVALS - 1 :ENEMIES(X, Y) = ETEMPLATE(ETYPE, Y) :NEXT Y :RETURN Notes *I use "static content" and "dynamic content" because "static array" and "dynamic array" have special meanings in some other programming languages. You don't need to worry about that at all for Petit! *Although you can't change the true size of an array after creating it, you can copy every element from that array into a new array that is larger (or smaller) if you need to. This approach is rather slow and should only be used when memory constraints are a serious concern. It's very unlikely you'd ever need to do this in Petit. Category:Tutorials Category:Resources Category:Kevin's Learning Petit Lessons